Wireless local area networks (WLANs) as defined e.g. in the IEEE 802.11 specifications are almost omnipresent today. The increase of throughput of the available channel was one major issue, and research has been focused on improving the modulation and coding within the physical protocol layer.
According to the 802.11 standard, wireless nodes or stations implement a distributed coordination function (DCF) which is a form of carrier sense multiple access with collision avoidance (CSMA/CA). CSMA/CA is a contention-based protocol making certain that all stations first sense the medium before transmitting. The main goal is to avoid having stations transmit at the same time, which results in collisions and corresponding retransmissions. If a station wanting to send a frame senses energy above a specific threshold on the medium (which could mean the transmission of another station), the station wanting access will wait until the medium is idle before transmitting the frame. The collision avoidance aspect of the protocol pertains to the use of acknowledgements that a receiving station sends to the sending station to verify error-free reception. Although somewhat more complex, this process of accessing the medium can be seen as a meeting where everyone is polite and each person only speaks when no one else is talking. In addition, participants who understand what the person is saying nod their head in agreement.
In a randomly operating backoff procedure, a station with a data packet to transmit generates a random number between 0 and a contention window (CW) size, which determines the duration of the backoff timer as counted in number of timeslots. The CW has a minimum starting value of 15, doubles after a collision, can rise up to 1023, and is decremented after a successful transfer, indicated by an acknowledgement (ACK) frame. After detecting the medium free for the duration of DCF Inter-Frame Space (DIFS), the mobile station counts down the backoff timer until it reaches zero and then starts its transmission. If during the countdown another mobile station occupies the medium, all mobile stations in backoff interrupt their count down and defer until they detect the medium free for at least DIFS. The standard includes an optional Request-to-Send (RTS)—Clear-to-Send (CTS) handshake prior to the transmission.
Recently, a combining of network coding with broadcast has been applied in 802.11-based multi-hop wireless networks to increase information content per transmission, and throughput benefits have been demonstrated for data applications.
FIG. 1 schematically depicts a topology of several wireless nodes. In the scenario presented in this figure, according to routing tables provided at each node, nodes 1 and 3 need to transmit their packets a and b to nodes 4 and 5, respectively. Node 2 has to act as a forwarder of these packet since nodes 4 and 5 are not radio range of node 1. According to the basic principle of network coding, node 2 broadcasts a coded packet (e.g. a⊕b), instead of forwarding packet a to node 4, and packet b to node 5. In this way, both nodes 4 and 5 can decode their original packet with just one broadcast transmission at the physical layer from node 2, instead of two dedicated transmissions. This can lead to a higher throughput. However, the practical schemes that have been proposed based on this principle, employ opportunistic coding and transmission of packets, which means that they are not robust for integration over existing Media Access Control (MAC) protocols. Furthermore, they require cross-layer interactions between the MAC and routing protocols that hamper the potential for clean solutions.
In a so-called “opportunistic approach” to network coding, a wireless node relies on local information to detect and exploit coding opportunities in real-time. If nodes participate in opportunistic listening, they snoop on all communications they hear over the wireless medium. The nodes may also annotate packets they send to tell their neighbours which packets they have heard. When a node sends, it may use its knowledge of what its neighbours have received to perform opportunistic coding, which could mean that the node can combine (e.g. XOR, “⊕”) multiple packets and send them in a single transmission if each intended receiver has enough information to decode its packet.
However, a problem that current wireless network coding schemes are faced with, is that nodes opportunistically overhear transmissions of packets not intended for them. For example in FIG. 1, node 1 transmits packet a that is intended for node 2, but it is overheard by node 5 who is in radio range of node 1 (and in radio range of node 2). However, with existing MAC protocols, nodes that are not the intended receivers (e.g. node 5 in FIG. 1) cannot acknowledge correct reception of overheard packets. This means that the node that employs a network coding algorithm (e.g. node 2 in FIG. 1), cannot know if the coding decisions it has made is the correct one. Incorrect coding decisions lead eventually to lower throughput which is far from the theoretically possible with network coding.
In Sachin Katti et al., “XORs in The Air: Practical Wireless Network Coding”, SIGCOMM, 2006, asynchronous out-of-band acknowledgments are proposed as a way to solve the above problem. However, with this approach, when a node decides which packets to code, it must still use a stochastic approach in order to estimate the fate of overheard packets. Clearly, this is not a viable approach for practical adoption of network coding.
Furthermore, another important problem is the hidden node problem. Consider for example that node 1 in FIG. 1 is transmitting packet a. However, node t2 is out of the radio range of node 1. If the MAC protocol is using a contention-based mechanism (like 802.11 DCF or the contention-based mechanism in WiMedia MAC), then node t2 will transmit a packet that will collide with the transmission of packet a from node 1. However, if node 5 is an opportunistic receiver and does not acknowledge the transmission, neither node 1 or 2 will know that it did not receive the packet. This fact disables node 2 from knowing deterministically what is the optimal coding decision it must make, regardless of the employed algorithm.